Hamilton: vertices matter.html (2673B)
1 <?xml version="1.0" encoding="UTF-8"?> 2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 <html><head><link rel="stylesheet" type="text/css" href="sitewide.css"><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/><meta name="exporter-version" content="Evernote Mac 7.1.1 (456663)"/><meta name="keywords" content="ng"/><meta name="altitude" content="-0.5295528173446655"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-04-24 10:31:01 +0000"/><meta name="latitude" content="52.33449063255681"/><meta name="longitude" content="4.866731888842327"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-05-25 22:35:15 +0000"/><title>Hamilton: vertices matter</title></head><body><div>a Hamilton cycle contains <span style="text-decoration: underline;">every</span> vertex <span style="text-decoration: underline;">exactly</span> once</div><div>G is Hamiltonian if it has a Hamilton cycle (but it’s hard to prove that it is, no efficient algorithm)</div><div>to show that G is not Hamiltonian:</div><ul><li><div>if G is Hamiltonian, then for any nonempty V* ⊆ V(G)</div></li><ul><li><div>the graph G-V* contains at most |V*| components</div></li><li><div>w(G-V*) ≤ |V*|</div></li></ul><li><div>if not true, graph not Hamiltonian</div></li></ul><div>Dirac’s criterion</div><ul><li><div>if G has n ≥ 3 vertices and ∀v: δ(v) ≥ n/2</div></li><li><div>then G is Hamiltonian</div></li></ul><div>Finding Hamilton cycles using Posa rotational transformations</div><ul><li><div>Pick starting vertex u. Initial path P=[u]</div></li><li><div>while P is not a Hamilton cycle:</div></li><ul><li><div>If possible, select y from N(last added vertex) excluding vertices already in path</div></li><ul><li><div>then add that y to the path</div></li></ul><li><div>else, pick a v from N(last added vertex). Because v is already in path, there is an edge from <i>v</i> to some other vertex <i>x</i>. </div></li><ul><li><div>do a switcherino — connect v to w, and reverse path from w to x:</div></li></ul><div style="margin-left: 40px;"><img src="Hamilton%3A%20vertices%20matter.resources/DE0A299C-0970-42AA-8FEE-B340BC1745E9.png" height="80" width="591"/><br/></div></ul></ul><div><br/></div><div>Traveling salesman problem:</div><ul><li><div>finding a shortest Hamilton cycle in a complete, weighted graph</div></li><li><div>because of Hamilton, there’s no efficient algorithm for this</div></li><li><div>greedy algorithm: start with arbitrary cycle, swap edges if it reduces overall weight</div></li></ul><div><br/></div></body></html>